// 阿里
// 自己创建树结构 判断是否子树
function TreeNode(val, right, left) {
  this.val = val === undefined ? 0 : val;
  this.right = right === undefined ? null : right;
  this.left = left === undefined ? null : left;
}

// function buildTree(arr, index) {
//   if (index > arr.length) return null;
//   let val = arr[index - 1];
//   if (!val) return null;
//   const treeNode = new TreeNode(val);
//   treeNode.left = buildTree(arr, index * 2);
//   treeNode.right = buildTree(arr, index * 2 + 1);
//   return treeNode;
// }

// const A = [3, 4, 5];
// const B = [1, 2, 3, null, null, 4, 5];

// console.log(buildTree(B, 1));

// // 或者这样 下标从0开始
// function buildTree2(arr, index) {
//   if (index >= arr.length) return null;
//   const val = arr[index];
//   const treeNode = new TreeNode(val);
//   treeNode.left = buildTree2(arr, index * 2 + 1);
//   treeNode.right = buildTree2(arr, index * 2 + 2);
//   return treeNode;
// }

// console.log(buildTree2(B, 0));

function arrToTree(arr, i = 0) {
  if (i < 0 || i >= arr.length || arr[i] === null) {
    return null;
  }
  let root = new TreeNode(arr[i]);
  root.left = arrToTree(arr, 2*i + 1);
  root.right = arrToTree(arr, 2 * i + 2);
  return root;
}